This invention relates to routing of data in computer networks.
In order for routers in such a network to store and forward data (ordinarily grouped into "packets"), each router needs to track current control information issued by other routers in the network. For example, if router A generates Ainfo(1), it is necessary for another router B to receive Ainfo(1). Later, when A generates Ainfo(2), router B needs to receive Ainfo(2). If a router C subsequently issues Cinfo(1), router B must track both Ainfo(2) and Cinfo(1), because Ainfo(2) is the latest information generated by router A and Cinfo(1) is the latest information generated by router C.
In one scheme for computing routes through a network, each router is responsible for ascertaining the identity of its neighbors, by following local handshaking protocols and generating special packets known as link state packets. Link state packets (LSPs) list each router's neighbors together with attributes of the links to the neighbors (such as "cost") which are of relevance to the routing algorithm. Each router periodically generates a new LSP which supersedes its previously generated LSPs. If the most recent LSPs are propagated reliably to all of the routers, each router has complete information about the current topology of the network and can thus use any well known algorithm for computing routes (such as Dijkstra's algorithm).
One way to indicate the relative age of LSPs among the LSPs of a given originating router is to assign a sequence number to each LSP. The sequence number is incremented for each new LSP. When a router receives a LSP, it compares that LSP's sequence number with the sequence number of any stored LSP from the same originating router. If the newly received LSP has a larger sequence number, it is stored in place of the previously stored LSP, otherwise not.
The sequence numbers are typically limited to a maximum value (2.sup.n -1 for an n-bit sequence number). Because the sequence number is incremented each time a new LSP is created by an originating router, the binary representation of the sequence number will eventually overflow. If the sequence number is allowed simply to roll over to zero, new LSPs will have lower sequence numbers than previous LSPs, and will be incorrectly ignored in favor of the previous, high numbered LSPs, creating system errors.
One way to reduce the frequency of sequence number overflow errors is to increase the size of the sequence number field. However, this solution is not infallible, as transmission errors in the communications links may create anomalies in LSPs transmitted through the faulty links. For example, a sequence number can be corrupted to a higher number, in which case the sequence number can overflow regardless of the size of the sequence number field.
Another way to deal with sequence number overflow errors is to represent the sequence number space as a circular space. A circular space uses specialized mathematics to compare two sequence numbers and determine which is more recent. For example, in an n-bit circular sequence number space, if two sequence numbers are within 2.sup.n-1 of each other, the larger number is assumed to be more recent. Otherwise, the smaller number is assumed to be more recent. (For later reference, sequence number spaces which do not use this type of specialized mathematics will be called linear spaces.) In a circular space, when a sequence number overflows from 2.sup.n to zero, the new sequence numbers with values near zero will be assumed to be more recent than the older sequence numbers with values near 2.sup.n. Other similar methods use a "lollipop" sequence number space, so named because, in a lollipop space, an n-bit sequence number, instead of overflowing from 2.sup.n to zero, begins with a linear space and, when incremented beyond a certain value, moves into and remains in a circular space. The mathematics for comparing sequence numbers are suitably modified to account for the lollipop overflow characteristic.
Several routers in a computer network are often grouped together, so that the routing of the group's data transmissions may be controlled by a single local authority. One way in which this is accomplished is to form a central "pseudo-router", through which each of the routers communicate with each other and the network. One of the routers in the group (the designated router) is responsible for the duties of the pseudo-router. LSPs indicating this fact are issued by the designated router. Often, it is necessary to transfer the duties of the designated router from one of the routers in the group to another router. In this case, the previously originated link state packets indicating the previous designated router must be renounced, and the new link state packets indicating the new designated router must be issued.
Another fault condition in a network is a router crash, where one of the routers stops working. Once a router crash is rectified, the router must be able to rejoin the network in a well-behaved manner.